package com.yun.algorithmproblem.leetcode;

import java.util.ArrayList;

public class Leetcode2787 {

    public static void main(String[] args) {
        Leetcode2787 obj = new Leetcode2787();
        int n = 226;
        int x = 1;
        System.out.println(obj.numberOfWays(n, x));
    }

    public int numberOfWays(int n, int x) {
        long[] dp = new long[n + 1];
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            int temp = (int) Math.pow(i + 1, x);
            if (temp > n) {
                break;
            }
            nums.add(temp);
        }
        dp[0] = 1;
        for (Integer num : nums) {
            for (int i = n; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return (int) (dp[n] % 1_000_000_007);
    }
}
